package com.example.demo.solution;


/**
 * @desc: 查找链表倒数指定位置数字<br/>
 * @author: Jingbo Hu<br/>
 * @time：2020年10⽉22⽇<br/>
 * @version：v1.0.0<br>
 */
public class NthFromEnd {
    public static Node findNthFromEnd(Node head, int n) {
        Node p1 = head;
        Node p2 = head;

        //把p2指针移动到正数第n个结点
        for (int i = 1; i < n; i++) {
            p2 = p2.next;
            if (p2 == null) {
                throw new IllegalArgumentException("参数n超出链表长度！");
            }
        }
        //p1和p2一起右移，直到p2指向链表尾结点
        while (p2.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }

    //快速创建链表
    public static Node buildLinkList(int[] array) {
        Node head = new Node(array[0]);
        Node p = head;

        for (int i = 1; i < array.length; i++) {
            Node next= new Node(array[i]);
            p.next =next;
            p = next;
        }
        return head;
    }

    //链表节点
    public static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        int[] inputs = {5, 3, 7, 2, 4, 1, 9, 8};
        Node head = buildLinkList(inputs);
        Node node = findNthFromEnd(head, 3);
        System.out.println("链表倒数第3个元素是：" + node.data);
    }
}
